package com.adamjwh.pratice.offer;

import com.adamjwh.tools.TreeNode;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
public class ConvertTree {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) {
            return null;
        }

        if(pRootOfTree.left == null && pRootOfTree.right == null) {
            return pRootOfTree;
        }

        //将左子树构成双向链表，返回头结点
        TreeNode left = Convert(pRootOfTree.left);

        //定位到左子树最右边的结点
        TreeNode p = left;
        while(p != null && p.right != null) {
            p = p.right;
        }

        //将root追加到左子树后
        if(left != null) {
            p.right = pRootOfTree;
            pRootOfTree.left = p;
        }

        //将右子树构成双向链表，返回头结点
        TreeNode right = Convert(pRootOfTree.right);

        //将右子树链表追加到root后
        if(right != null) {
            right.left = pRootOfTree;
            pRootOfTree.right = right;
        }

        return left != null ? left : pRootOfTree;
    }
}
